package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/15 11:03
 * @description :12道。刷刷剑指Offer
 * 城墙之行圆满结束，永宁门->长乐门->安远门->安定门。学习生活也该回归正轨了。
 * persevere to last
 * 2021.11.15
 * 2021年11月15日21:25:55
 * 李红磊
 */
public class t20211115 {

    //319.灯泡开关
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }

    //剑指06.从尾到头打印链表
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[0];
        if (head.next == null) return new int[]{head.val};

        int len = 0;
        ListNode temp = head;
        while (true) {
            if (temp.next == null) {
                len++;
                break;
            }
            len++;
            temp = temp.next;

        }
        temp = head;
        int[] res = new int[len];
        for (int i = len - 1; i >= 0; i--) {
            res[i] = temp.val;
            temp = temp.next;
        }
        return res;
    }

    //剑指24.反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode temp = head;
        ListNode dummy = new ListNode(-1);

        while (true) {
            if (temp.next == null) {
                ListNode d_next = dummy.next;
                temp.next = d_next;
                dummy.next = temp;
                break;
            }

            ListNode d_next = dummy.next;
            ListNode k = temp.next;
            temp.next = d_next;
            dummy.next = temp;

            temp = k;

        }
        return dummy.next;
    }

    //剑指35.复杂链表的复制
    public Node copyRandomList(Node head) {
        if (head == null || head.next == null) return head;


        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));//原节点：新节点
            cur = cur.next;
        }

        cur = head;
        //构建新链表
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }

    //剑指5。替换空格
    public String replaceSpace(String s) {
        return "";
    }

    //剑指58.左旋字符串
    public String reverseLeftWords(String s, int n) {
        return s.substring(0, n) + s.substring(n);
    }

    //剑指3.数组中重复的数字
    public int findRepeatNumber(int[] nums) {
        return -1;
    }

    //剑指53。在排序数组中查找数字1
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;
        int ans = 0, len = nums.length;
        int left = 0, right = len - 1;

        while (left <= right) {
            int mid = left + right >>> 1;
            if (nums[mid] == target) {
                ans++;
                for (int i = left; i < mid; i++) {
                    if (nums[i] == target) ans++;
                }
                for (int k = mid + 1; k <= right; k++) {
                    if (nums[k] == target) ans++;
                }
                return ans;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }
        return ans;
    }

    //剑指53. 0~n-1中缺失的数字
    public int missingNumber(int[] nums) {
        return 1;
    }

    //剑指04.二维数组中的查找
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        return false;
    }

    public static void main(String[] args) {
        t20211115 t20211115 = new t20211115();
        System.out.println(t20211115.search(new int[]{1,2,3,3,3,3,4,5,9}, 3));

    }

}

//剑指09.用两个栈实现队列
class CQueue {

    ArrayDeque mainStack;
    ArrayDeque assistStack;


    public CQueue() {
        mainStack = new ArrayDeque();
        assistStack = new ArrayDeque();
    }

    public void appendTail(int value) {
        mainStack.push(value);
    }

    public int deleteHead() {
        if (mainStack.isEmpty()) return -1;
        while (!mainStack.isEmpty()) {
            assistStack.push(mainStack.pop());
        }
        int res = (int) assistStack.pop();
        while (!assistStack.isEmpty()) mainStack.push(assistStack.pop());
        return res;
    }
}

//剑指30.包含min函数的栈
class MinStack {
    private List<Integer> list;
    private ArrayDeque<Integer> stack;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        list = new ArrayList<>();
        stack = new ArrayDeque<>();
    }

    public void push(int x) {
        list.add(x);
        stack.push(x);
        Collections.sort(list);
    }

    public void pop() {
        if (stack.isEmpty()) return;
        int num = stack.pop();
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == num) list.remove(i);
        }
        Collections.sort(list);
    }

    public int top() {
        if (stack.isEmpty()) return -1;
        return stack.peek();
    }

    public int min() {
        if (stack.isEmpty()) return -1;
        return list.get(0);
    }

}

class MinStack2 {
    private ArrayDeque main, assit;

    /**
     * initialize your data structure here.
     */
    public MinStack2() {
        main = new ArrayDeque<Integer>();
        assit = new ArrayDeque<Integer>();
    }

    public void push(int x) {
        main.push(x);

        if (assit.isEmpty() || (int) assit.peek() >= x) assit.push(x);

    }

    public void pop() {
        if (main.pop().equals(assit.peek())) assit.pop();
    }

    public int top() {
        return (int) main.peek();
    }

    public int min() {
        return (int) assit.peek();

    }
}
